import copy

grammar5 = {
    "terminals": {"x", "y", "$"},
    "non_terminals": {"S'", "S", "T"},
    "start": "S'",
    "productions": [
        ("S'", ["S", "$"]),  # S' :== S$
        ("S", ["x","x","T"]),  # S :== xxT
        ("T", ["y"]), # T :== y
    ],
}
print(grammar5)
AnalyzerTable = {
    # 状态1
    '1': {'x': 's2', 
          'y': '', 
          '$': '',
          'S': 'g6',
          'T': ''
          },
    # 状态2
    '2': {'x': 's3', 
          'y': '', 
          '$': '',
          'S': '',
          'T': ''
          },
    # 状态3
    '3': {'x': '', 
          'y': 's4', 
          '$': '',
          'S': '',
          'T': 'g5'
          },
    # 状态4
    '4': {'x': 'r2', 
          'y': 'r2', 
          '$': 'r2',
          'S': '',
          'T': ''
          },
    # 状态5
    '5': {'x': 'r1', 
          'y': 'r1', 
          '$': 'r1',
          'S': '',
          'T': ''
          },
    # 状态6
    '6': {'x': '', 
          'y': '', 
          '$': 'accept',
          'S': '',
          'T': ''
          },       
}
print(AnalyzerTable)

# LR0语法分析
def LR0Analyzer(Grammar, InputStr):
    StackState = ['1']  # 状态栈初始状态为1
    StackInput = []  # 输入栈
    CurInputIndex = 0 # 当前输入字符索引
    while len(StackState) > 0 : # 当状态栈不为空
        TopState = StackState[-1] # 获取当前状态
        TopSymbol = StackInput[-1] if len(StackInput) > 0 else ''
        if TopSymbol !='': # 如果输入栈不为空，看能否进行归约和状态转移
            TopState = StackState[-1] # 状态发生变化，获取当前状态
            TopSymbol = StackInput[-1]
            Action = AnalyzerTable[TopState][TopSymbol]
            while (Action != '') and ((Action[0] == 'r') or (Action[0] == 'g')):
                if Action[0] == 'r':  # 规约动作
                    Production = Grammar["productions"][int(Action[1]) - 1]
                    ProdRight = Production[1] # 获取产生式右部
                    ProdLeft = Production[0]# 获取产生式左部                                        
                    for i in range(len(ProdRight)):
                        StackState.pop()
                        StackInput.pop()
                    StackInput.append(ProdLeft) # 将产生式左部压入输入栈
                if Action[0] == 'g':  # 状态转移动作
                        StackState.append(Action[1]) #转移状态
                print('StackInput: ', StackInput)
                print('StackState: ', StackState)
                #重新检查当前状态和当前输入字符是否有动作
                TopState = StackState[-1] # 状态发生变化，获取当前状态
                TopSymbol = StackInput[-1]
                Action = AnalyzerTable[TopState][TopSymbol]


        #非终结符导致的状态转移处理完以后，看有没有下一个输入字符
        if CurInputIndex <= len(InputStr)-1: # 如果当前输入字符索引小于输入字符串长度，则获取当前输入字符
            TopSymbol = InputStr[CurInputIndex]
            StackInput.append(TopSymbol) # 压入当前输入字符
            CurInputIndex += 1
            print('StackInput: ', StackInput)
            print('StackState: ', StackState)
            TopState = StackState[-1] # 获取当前状态
            TopSymbol = StackInput[-1]
            Action = AnalyzerTable[TopState][TopSymbol]
            if Action == '':  # 如果没有动作，则报错
                print("Error: No such action")
                return False
            if Action[0] == 's':
                StackState.append(Action[1]) #转移状态
                # 如果当前状态是规约动作，则执行规约动作
            elif Action[0] == 'a':             
                print("Accepted")  
                return True
        #while end
    return False

print("LR0 Analyzer Testing 1 --------------------------------")
InputString = "xxy$"
Rst = LR0Analyzer(grammar5, InputString)  
print(f"The syntax of {InputString} is {Rst}")

print("LR0 Analyzer Testing 2 --------------------------------")
InputString = "xyy$"
Rst = LR0Analyzer(grammar5, InputString)  
print(f"The syntax of {InputString} is {Rst}")

